1832E - Combinatorics Problem - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f(i,x,n) for(int i = x; i < n; i++)
#define fr(i,x,n) for(int i = n - 1; i >= x; i--)
#define pb push_back
#define pf push_front
#define mod 998244353
#define endl '\n'
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef long double ld;
 
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};


int main(){
    fast_io
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif

    ll n, a, x, y, m, k;
    cin >> n >> a >> x >> y >> m >> k;

    vll A(n + 1), pref(n + 1, 0);
    A[1] = a;
    pref[1] = a;
    f(i,2,n + 1){
        A[i] = (A[i - 1] * x + y) % m;
        pref[i] = (pref[i - 1] + A[i]) % mod;
    }
    
    vector <vll> dp(n + 1, vll (k + 1, 0));
    dp[1][0] = A[1];
    dp[1][1] = A[1];

    f(i,2,n + 1){
        f(j,0,k + 1){
            if(j == 0) dp[i][j] = pref[i];
            else{
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] + (j == 1 ? A[i] : 0)) % mod;
            }
        }
    }
    // b[1] = 0;
    // b[2] = 8;
    // b[3] = 24 + 19 = 43
    // b[4] = 48 + 57 + 41 = 146 

    ll ans = 0;
    f(i,1,n + 1){
        ans ^= i * dp[i][k];
    }

    cout << ans << endl;

    return 0;
}